These teachings relate generally to computer-implemented methods and apparatus for representing and modeling surfaces, including techniques that use a Catmull-Clark surface representation.
Interactive editing is an important element of model creation for a variety of applications, ranging from mechanical design to movie character creation. Modeling typically begins with an existing object on which the user performs a sequence of editing operations that lead to the desired shape. Of particular interest to these teachings are small-scale features such as engravings and embossed details that are encountered on many real-life objects.
Traditionally, geometric modeling has relied on non-uniform rational B-splines (NURBS) for surface design. However, NURBS have well-known limitations, such as an inability to address arbitrary topology, tedious cross-boundary continuity management, and a difficulty in representing different resolution levels. In addition, editing operations such as those considered herein typically require features to be aligned with iso-parameter lines or patch boundaries or other complex manipulations in parameter space.
While techniques such as free-form deformations, wires, and procedural modeling offer alternative ways to edit three-dimensional objects, typically they do not present a unified representation that includes both the original surface and the edits. Thus, in many cases, the resulting representation is not the same as the original, but an extension of it. The main drawback of this approach is that algorithms that have been developed for the original representation are not directly applicable to the result and special cases may have to be considered.
The past few years have seen considerable advances in subdivision theory, and many common NURBS operations have been translated into the subdivision setting. Subdivision theory, parametric evaluation, and applications such as interactive editing, trimming, Boolean operations, and geometry compression have contributed to the increasing popularity of multiresolution subdivision surfaces. To date, they have been used in commercial modelers (e.g., Alias/Wavefront""s Maya, Pixar""s Renderman, Nichimen""s Mirai, and Micropace""s Lightwave 3D), and are currently being employed in game engines and hardware implementations.
Subdivision algorithms are attractive because of their conceptual simplicity and efficiency with which they can generate smooth surfaces starting from arbitrary meshes. Multiresolution subdivision surfaces offer additional flexibility by allowing modeling of detail at different resolution levels and ensuring that fine-scale edits blend naturally with coarse shape deformations.
Subdivision surfaces permit an efficient representation of free-form surfaces of arbitrary topology. A subdivision surface is defined over an initial control mesh and a subdivision scheme is used to recursively refine the control mesh by recomputing vertex positions and inserting new vertices according to certain rules (masks). Recursive subdivision produces a hierarchy of meshes that converge to a smooth limit surface.
Most objects of interest to geometric design, however, are only piecewise-smooth, and typically exhibit sharp creases and corners. To model these sharp creases and corners using subdivision, special rules are needed to avoid the smoothing of the desired sharp details.
Reference in this regard can be made to FIGS. 1A, 1B and 1C, wherein surface editing processes are depicted. In FIG. 1A features are added to an initial surface. It should be apparent that smooth and sharp features are fundamentally different: smooth features (FIG. 1B) add bumps to the surface, while sharp features create tangent plane discontinuities (FIG. 1C). Previous work in this area has focused on defining the special rules required to define these surface features.
Hoppe et al. introduced rules to create sharp features on subdivision surfaces. DeRose et al. extended the approach of Hoppe et al. to achieve creases of controllable sharpness by using subdivision rules parameterized by a sharpness factor. Reference can also be made to the curve interpolation work of Nasri.
In all of these techniques, there is the common requirement that features need to be aligned with the edges of the underlying control mesh. Therefore, the control mesh is designed with a particular feature in mind. However, a designer might want to first model an initial shape and then apply small-scale features in later stages of the design. The currently available modeling techniques do not adequately support this type of a modeling approach, and thus also do not allow features to be placed at arbitrary locations on the surface.
Multiresolution subdivision surfaces are a natural extension of subdivision surfaces that accommodate editing of details at different scales, allowing general shape deformations as well as the creation of minute features. Multiresolution, however, does not solve the problem of sharp features, as these types of features can only be placed along edges at discrete locations in the mesh hierarchy.
Reference can be made to Khodakovsky and Schroder, who describe a method for interactive creation of feature curves at arbitrary locations on a surface. To create a feature along a curve, a perturbation according to a given profile is applied in the neighborhood of the curve, while maintaining smooth boundary conditions. There are no restrictions on the position of the curve with respect to the underlying surface, however, the representation used is no longer a pure multiresolution surface. In order to create a sharp feature with this technique, it is necessary to enforce the feature profile at each level of the multiresolution hierarchy. Both the surface and the feature curve are required to represent the resulting surface. Thus, one cannot directly apply subdivision surface operations (i.e., evaluation).
Trimming is an important design operation, however, it has been traditionally difficult to perform trimming for parametric surfaces. One conventional approach is described by Litke et al., where quasi-interpolation is used to approximate a trimmed surface with a combined subdivision surface.
It should thus be apparent that the teachings of the prior art do not adequately address the problem of defining certain features, such as surface creases at arbitrary surface locations, in an efficient and computationally efficient manner.
The foregoing and other problems are overcome by methods and apparatus in accordance with embodiments of these teachings.
These teachings address the problems of feature placement and feature creation by providing a set of tools that allow fine-scale editing and trimming operations to be applied at any desired location on a surface. Multiresolution subdivision surfaces are preferably employed as the model representation, and this representation is preserved after editing, thereby providing flexibility to integrate this technique with other algorithms developed for multiresolution subdivision surfaces.
In the preferred implementation a subdivision scheme for quadrilateral meshes is used. However, these teachings can also be practiced using algorithms developed for triangular meshes.
An aspect of these teachings is an algorithm to produce sharp features at arbitrary locations on a piecewise-smooth multiresolution surface, without requiring that one remesh the control mesh. The sharp features can be created interactively, along curves drawn by the user on the target surface.
A further aspect of these teachings is the provision of an extended set of rules for the Catmull-Clark subdivision scheme that allow the creation of creases and boundaries along diagonals of quadrilateral mesh faces.
Another aspect of these teachings is the provision of a unified solution to offsetting and trimming operations. Using the presently preferred embodiment a sharp crease having a user-defined profile may be applied along a given curve. Alternatively, the portion of the surface delimited by the curve can be trimmed off, creating a hole in the surface.
These teachings extend conventional subdivision schemes for piecewise-smooth surfaces, where control mesh vertices and edges are tagged in order to generate singularities, such as creases, darts, and corners.
The inventive technique removes the conventional constraints related to feature placement by allowing sharp features to be created and edited along any user-defined set of curves on the mesh. These teachings view subdivision surfaces as parametric surfaces defined over the coarsest-level mesh, and compute the image of a given curve in the parametric domain. The technique then reparameterizes the surface to align the parameterization with the curve on some level of the multiresolution hierarchy. Subsequently, special rules are applied to generate non-smooth features.
In accordance with these teachings the issue of sharp features is addressed, enabling them to be placed arbitrarily in a multiresolution subdivision setting, thus allowing greater flexibility in combining feature editing with other existing subdivision tools.
A benefit of the use of this method is an ability to perform trimming of surfaces by simply discarding the portion of surface inside of a given curve.
Further with regard to trimming, quasi-interpolation may be combined with these teachings to obtain trimmed multiresolution surfaces within a specified tolerance.
Disclosed herein is an efficient method for creating sharp features along an arbitrarily positioned set of curves on a Catmull-Clark multiresolution subdivision surface. The surface is viewed as a parametric surface defined over the initial control mesh, and the method recomputes the parameterization to align it with a pre-image of the feature curves in the parameter domain. The result is a surface represented in the same way as the input surface, with the curves passing through mesh edges or face diagonals. This property enables the application of special subdivision rules along the curve to create sharp profiles.
A further application of the presently preferred algorithm is trimming, which can be achieved simply by discarding the portion of the mesh situated within the trim curve.
The algorithm takes as input arbitrarily shaped curves, with or without self-intersections, as well as multiple intersecting curves. The number of curves intersecting at a point, however, is preferably limited by the number of connections available between a vertex and its neighbors along edges and diagonals (eight in the regular case). However, multiresolution surface representations that allow for topology changes within the hierarchy may be used to resolve this restriction. Other application areas may combine quasi-interpolation or surface fitting with the trimming approach. Also, it is believed that the special diagonal subdivision rules are useful in a general geometric modeling context.
A method in accordance with these teachings represents a sharp feature on a surface of a model, and includes steps of defining at least one feature curve on the surface; reparameterizing the surface; and creating the feature on the reparameterized surface so as to be generally coincident with the feature curve, where the feature lies along boundaries between piecewise-smooth patch surfaces where patch surfaces with distinct tangent planes are joined. The surface is reparameterized by moving a control mesh relative to the surface to sample the feature curve with vertices of the control mesh, and creating the feature includes a subdivision step where edges and diagonals are treated as creases in the control mesh, and piecewise-smooth subdivision rules are applied to obtain a sharp feature on the surface.